package com.jeff.practice;

public class NumIslandsDFS {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int rows = grid.length;
        int cols = grid[0].length;
        // 创建一个二维数组，用于记录每个位置是否被访问过
        boolean[][] visited = new boolean[rows][cols];
        int islandCount = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                //已经被访问过的 则不用重复访问 只会统计一次
                if (grid[r][c] == '1' && !visited[r][c]) {
                    //深度优先搜索
                    dfs(grid, visited, r, c);
                    islandCount++;
                }
            }
        }

        return islandCount;
    }

    private void dfs(char[][] grid, boolean[][] visited, int r, int c) {
        // 边界条件
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == '0' || visited[r][c]) {
            return;
        }

        // 标记为已访问
        visited[r][c] = true;

        // 递归访问上下左右四个方向
        dfs(grid, visited, r + 1, c); // 下
        dfs(grid, visited, r - 1, c); // 上
        dfs(grid, visited, r, c + 1); // 右
        dfs(grid, visited, r, c - 1); // 左
    }

    public static void main(String[] args) {
        NumIslandsDFS solution = new NumIslandsDFS();
        char[][] grid = {
            {'0', '1', '0', '0', '0'},
            {'1', '0', '0', '1', '1'},
            {'0', '0', '0', '0', '0'},
            {'0', '1', '1', '0', '0'},
        };
        System.out.println(solution.numIslands(grid)); // 输出: 3
    }
}
